//给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 
//
// 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。 
//
// 例如, 
//
// 
//给定二叉搜索树:
//
//        4
//       / \
//      2   7
//     / \
//    1   3
//
//和 插入的值: 5
// 
//
// 你可以返回这个二叉搜索树: 
//
// 
//         4
//       /   \
//      2     7
//     / \   /
//    1   3 5
// 
//
// 或者这个树也是有效的: 
//
// 
//         5
//       /   \
//      2     7
//     / \   
//    1   3
//         \
//          4
// 
// Related Topics 树 
// 👍 77 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

/**
 * Java：二叉搜索树中的插入操作
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P701_InsertIntoABinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new P701_InsertIntoABinarySearchTree().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 迭代
     * 时间复杂度 O(logn)
     * 空间复杂度 O(1)
     */
    class Solution {
        public TreeNode insertIntoBST(TreeNode root, int val) {
            TreeNode newNode = new TreeNode(val);
            TreeNode node = root;
            while (node != null) {
                if (val < node.val) {
                    if (node.left == null) {
                        node.left = newNode;
                        return root;
                    } else {
                        node = node.left;
                    }
                }
                if (val > node.val) {
                    if (node.right == null) {
                        node.right = newNode;
                        return root;
                    } else {
                        node = node.right;
                    }
                }
            }

            return newNode;
        }

    }
    ///**
    // * 递归
    // * 时间复杂度 O(logn)
    // * 空间复杂度 O(n)
    // */
    //class Solution {
    //    public TreeNode insertIntoBST(TreeNode root, int val) {
    //        if (root == null) {
    //            return new TreeNode(val);
    //        }
    //        traverseAndAdd(root, val);
    //        return root;
    //    }
    //
    //    private void traverseAndAdd(TreeNode root, int val) {
    //        if (root.left == null && root.val > val) {
    //            root.left = new TreeNode(val);
    //            return;
    //        }
    //        if (root.right == null && root.val < val) {
    //            root.right = new TreeNode(val);
    //            return;
    //        }
    //        traverseAndAdd(root.val > val ? root.left : root.right, val);
    //    }
    //}
    //leetcode submit region end(Prohibit modification and deletion)

}
